In general information processing devices, a lookup table, which contains a correspondence information storage unit, such as a memory storing computation result (output data) corresponding to the input data in each address, may be used to make computing processing to determine the output data corresponding to the input data faster. By referring to the address corresponding to the input data and acquiring the output data stored in an address, the output data corresponding to the input data is more quickly accessed than actually computing it.
FIG. 1 is an example of a system where a lookup table is used. This example shows the status when receive signals are demodulated in CDMA (Code Division Multiple Access) in a mobile communication system or in OFDM (Orthogonal Frequency Division Multiplexing) in a next generation mobile communication system. When signals are demodulated, Fourier transform or fast Fourier transform is performed to extract the frequency component of the receive signals, and to make such a transform faster the values of sine and cosine must be acquired at high speed.
In FIG. 1, the signal received by the antenna 1 are transformed by the A/D (analog/digital) converter 2, and when the processing to extract the frequency component is performed in the Fourier transform device 3 after this, the angle information is input and the correspondence information storage unit 5 in the lookup table 4 is referred to to determine the sine and cosine values corresponding to the angle information as the output data.
FIG. 2 is a diagram depicting the conventional lookup table. The trigonometric function value corresponding to the angle information of the input data has been stored in each address as the output data in advance. In the example in FIG. 2, 5-bit input data (00101) is input to the lookup table 4, and the address (00101) is referred to by the correspondence information storage unit 5, and as a result the output data (+0.010) is acquired.
As FIG. 2 shows, in the case of a conventional lookup table where one address corresponds to one input data and one output data corresponds to that address, the memory capacity required for the lookup table increases as the addresses corresponding to the input data increase. Also as the number of bits used for the address increases, the memory capacity required for the lookup table increases. Therefore some methods to decrease the memory capacity required for the lookup table have been proposed (Japanese Patent Application Laid-Open No.H10-300517, No.H5-183443 and No.2000-341546).
Japanese Patent Application Laid-Open No.H10-300517 discloses an interpolation circuit of an encoder where instead of referring to the lookup table using all the bits of the digital data to be input, the digital data to be input is divided into high order bits and low order bits, and high order bits are used for referring to the lookup table, and low order bits are used for interpolation calculation. According to Japanese Patent Application Laid-Open H10-300517, the memory capacity required for the lookup table can be decreased compared with prior art since low order bits are not used for referring to the lookup table.
However even if the number of bits of an address is decreased and the memory capacity required for the lookup table is decreased by decreasing the number of addresses, still only one output data corresponds to one address in the lookup table, and if the number of high order bits increases, the memory capacity required for the lookup table still increases, therefore improvement was necessary for the conventional approach of decreasing memory capacity. In the case of Japanese Patent Application Laid-Open No.H5-183443 and No.2000-341546 as well, only one output data corresponds to one address, where the same problem as Japanese Patent Application Laid-Open No.H10-300517 remains.